package april;

import javax.xml.bind.annotation.XmlID;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-4-27 20:28
 * @description：
 * @modified By：
 * @version:
 */
public class April27 {
    /**
     * create by: 冯涛滔
     * description: 用二分查找
     * 会出现几种情况
     * 如果数组只有一个数 那么 left==fight 循环不走 直接输出left
     * 1. 左值 < 中值, 中值 < 右值 ：没有旋转，最小值在最左边，可以收缩右边界
     * 2. 左值 > 中值, 中值 < 右值 ：有旋转，最小值在左半边，可以收缩右边界
     * 3. 左值 < 中值, 中值 > 右值 ：有旋转，最小值在右半边，可以收缩左边界
     * create time: 2020-4-27 20:43
     * @params [nums]
     * @return int
     */
    public static int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
    public static int searchFindMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    public  static int findTarget2(int[] nums,int left,int right,int target){
        while(left<right){
            int mid = left+(right-left)/2;
            if(target==nums[left]){
                return left;
            }
            if(target>nums[mid]){//右半边
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }
    /**
     * create by: 冯涛滔
     * description: 垃圾算法 靠着上一题的找出最小值 把一个数组分成两个 二分搜索
     * create time: 2020-4-27 22:05
     * @params [nums, target]
     * @return int
     */
    public static int search(int[] nums, int target) {

        if(nums.length==0){
            return -1;
        }
        int right = nums.length-1;
        int left = 0;
        int min = searchFindMin(nums);//最小的位置的边界
        if(target<=nums[right]){ //这个数字在最小值到最右边这个区间 不管数组怎么旋转从最小值到最右边一定是升序数组
            left = findTarget2(nums,min,right,target);
        }else{
            if(min!=0&&nums[min-1]>=target){ //这个数字在另一个区间
                left= findTarget2(nums,0,min-1,target);
            }else{
                return -1; //比所有值都大那么就只能是-1了
            }
        }
        if(nums[left]==target){
            return left;
        }else {
            return -1;
        }
    }
    /**
     * create by: 冯涛滔
     * description: 直接在这个旋转了的数组进行查找
     * create time: 2020-4-27 22:37
     * @params [nums, target]
     * @return int
     */
    public static int search2(int[] nums, int target) {
        int right = nums.length-1;
        int left = 0;
        int mid = 0;
        while(left<=right){ //这里的=于是考虑到数组只有一个元素省的多写一个判断
            mid = left+(right-left)/2;
            if(nums[mid]==target){ //当遍历到最后一个的时候因为计算公式是向下取整所以会是left
                return mid;
            }
            if(nums[left]<=nums[mid]){ //先判断从left到mid这段数组是否是升序的 =是考虑到数组可能会有重复的选项
                //正常的升序 再次判断 target在mid的左边还是右边
                if (target >= nums[left] && target < nums[mid]) { //确认在左半边 缩小右半区
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }else{ //乱序了
                if(target>nums[mid]&&target<=nums[right]){
                    //虽然乱了但是target的值是在乱了的那边也就是右边 缩小左半区
                    left = mid+1;
                }else{
                    //不管怎么样从最小值到右半区肯定是没有他了 将右半区砍掉
                    right = mid;
                }

            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] nums = {3,5,1};
        System.out.println(search2(nums, 5));
    }
}
